package com.yangzhe.algorithm.c006;

import java.util.Arrays;

// 有序数组中找>=num的最左位置
public class Code02_FindLeft {
    public static void main(String[] args) {
        // 随机长度范围
        int arrMax = 10;
        // 数组数量级
        int numberMax = 10;
        // 测试次数
        int testCount = 1000;

        // 1. 数组长度


        System.out.println("测试开始");
        for (int i = 0; i < testCount; i++) {
            int searchNumber = 10;
            int randomArrayLength = (int) (Math.random() * arrMax) + 1;
            int[] arr = randomArray(randomArrayLength, numberMax);
            Arrays.sort(arr);
           // printArray(arr);
            int binarySearch = findLeft(arr, searchNumber);
            //System.out.println("二分：" + binarySearch);
            int bruteForceSearch = bruteForceFindLeft(arr, searchNumber);
            //System.out.println("暴力" + bruteForceSearch);
            if (binarySearch != bruteForceSearch) {
                System.out.println("测试失败");
            }
        }

        System.out.println("测试完成");
    }

    public static void printArray(int[] arr) {
        StringBuilder sb = new StringBuilder();
        for (int i : arr) {
            sb.append(i + ",");
        }

        System.out.println(sb.toString());
    }

    public static int[] randomArray(int length, int n) {
        int[] arr = new int[length];
        for (int i = 0; i < length; i++) {
            arr[i] = (int) (Math.random() * n) + 1;
        }

        return arr;
    }

    public static int findLeft(int[] arr, int num) {
        int answer = -1;
        if (arr == null || arr.length == 0) {
            return answer;
        }
        int l = 0;
        int r = arr.length - 1;

        while (l <= r) {
            // 防止l + r整数溢出 通分之后 (2l + r - l) / 2 = (r + l) / 2
            int m = l + (r - l) / 2;
            if (arr[m] >= num) {
                answer = m;
                r = m - 1;
            } else {
                l = m + 1;
            }
        }

        return answer;
    }

    public static int bruteForceFindLeft(int[] arr, int num) {
        int answer = -1;
        if (arr == null || arr.length == 0) {
            return answer;
        }
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] >= num) {
                return i;
            }
        }

        return answer;
    }
}
